package com.hy.study.linkedlist;

import java.util.Stack;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        Node sj = new Node(1, "宋江", "及时雨");
        Node ljy = new Node(2, "卢俊义", "玉麒麟");
        Node wuyong = new Node(3, "吴用", "智多星");
        Node linchong = new Node(4, "林冲", "豹子头");
        SingleLinkedList linkedList = new SingleLinkedList();
//        linkedList.add(sj);
//        linkedList.add(ljy);
//        linkedList.add(wuyong);
//        linkedList.add(linchong);
        linkedList.addByOrder(wuyong);
        linkedList.addByOrder(linchong);
        linkedList.addByOrder(sj);
        linkedList.addByOrder(ljy);
        System.out.println("逆序打印链表结构没有改变结构:==========start");
        reversePrint(linkedList.getHead());
        System.out.println("逆序打印链表结构没有改变结构:==========end");
        linkedList.list();
        System.out.println("但链表中有效节点个数:" + getLength(linkedList.getHead()));
        System.out.println("得到倒数第3个的元素是:" + findLastNodeIndex(linkedList.getHead(), 5));
        Node ljy2 = new Node(2, "小鲁", "玉麒麟～～～");
        linkedList.update(ljy2);
        System.out.println("-------------修改之后-----------");
        linkedList.list();
        System.out.println("查询得到:" + linkedList.get(2));

        //测试但链表的反转


        reverseList(linkedList.getHead());
        linkedList.list();

        linkedList.delete(1);
        linkedList.delete(4);
        linkedList.delete(3);
        linkedList.delete(2);
        System.out.println("----------删除之后的");
        linkedList.list();
    }

    /**
     * 将但链表反转
     *
     * @param head
     */
    public static void reverseList(Node head) {
        //如果链表为空或者 只有一个节点，就无需反转 直接返回
        if (head.getNextNode() == null || head.getNextNode().getNextNode() == null) {
            return;
        }
        Node temp = head.getNextNode();
        Node next = null;//指向当前节点的下一个节点
        Node reverseHead=new Node(0,"","");
        //遍历原理的链表
        while (temp!=null){
            //没遍历一个节点 取出 并放在新的链表中
            next=temp.getNextNode();//暂时保存当前节点的下一个节点
            temp.setNextNode(reverseHead.getNextNode());//将temp 的下一个节点指向新的链表的最前端
            reverseHead.setNextNode(temp);//将temp 链接到新的链表上
            temp=next;//后移
        }
        //将head.next 指向reverseHead.next
        head.setNextNode(reverseHead.getNextNode());
    }


    /**
     * 查询单链表倒数第k个节点
     * 1.先遍历整个链表得到链表的长度 size
     * 2.再次从第一个遍历到(size-index)个
     * 3.找到返回该节点，否则返回null
     */
    public static Node findLastNodeIndex(Node head, int index) {
        if (head.getNextNode() == null) {
            return null;
        }
        int size = getLength(head);
        if (index <= 0 || index > size) {
            return null;
        }
        Node temp = head.getNextNode();
        for (int i = 0; i < (size - index); i++) {
            temp = temp.getNextNode();
        }
        return temp;
    }


    /**
     * 获取单列表中的节点个数(如果带头节点，需求不统计头节点)
     *
     * @return
     */

    public static int getLength(Node head) {
        if (head.getNextNode() == null) {
            //空链表
            return 0;
        }
        int length = 0;
        Node temp = head.getNextNode();
        while (temp != null) {
            length++;
            temp = temp.getNextNode();
        }
        return length;
    }

    /**
     * 逆序打印单链表
     * 1.方法一：先将单链表进行反转，然后遍历即可，，这样做会破坏原来的链表结构(不推荐)
     * 2.方法二:可以利用栈这个数据结构，将各个节点压入栈，利用栈的先进后出的特点实现逆序打印
     */
    public static  void reversePrint(Node head){
        if(head.getNextNode()==null){
            return;
        }
        Stack<Node> nodeStack=new Stack<Node>();
        Node curr=head.getNextNode();
        //将链表的所有节点压入栈中
        while(curr!=null){
            nodeStack.push(curr);
            curr=curr.getNextNode();
        }
        //遍历输出栈
        while(nodeStack.size()>0){
            //根据先进先出的特性 弹
            System.out.println(nodeStack.pop());
        }
    }

    /**
     * 合并两个有序链表，合并完成之后 也是一个有序的链表
     */
}

//定一个一个SingleLinkedList 来管理节点
class SingleLinkedList {
    //初始化一个头节点,一般头节点不让动 不存放具体的数据
    private Node head = new Node(0, "", "");

    //添加节点到单项链表
    // 1.当不考虑编号顺序是 找到链表的最后节点
    // 2.将最后的这个节点的next 指向新的节点
    public void add(Node node) {
        //头节点不能动
        Node temp = head;
        //变量链表，找到最后
        while (true) {
            if (temp.getNextNode() == null) {
                break;
            }
            //如果没有找到最后 将temp 后移
            temp = temp.getNextNode();
        }
        //当退出while 循环时 temp 指向了链表的最后
        temp.setNextNode(node);
    }

    /**
     * 显示链表[遍历]
     */
    public void list() {
        //判断链表是否为空
        if (head.getNextNode() == null) {
            System.out.println("链表为空");
            return;
        }

        //头节点不能动
        Node temp = head.getNextNode();
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            //将next 后移
            temp = temp.getNextNode();
        }


    }


    /**
     * 修改节点信息，根据no 编号来修改，即no 编号不能改
     *
     * @param node
     */
    public void update(Node node) {
        if (head.getNextNode() == null) {
            System.out.println("链表为空");
            return;
        }


        Node temp = head.getNextNode();
        boolean flag = false;//表示是否找该节点
        while (true) {
            if (temp == null) {//表示链表已经遍历结束了
                break;
            }
            if (temp.getNo() == node.getNo()) {
                flag = true;//找到了
                break;
            }
            temp = temp.getNextNode();
        }
        if (flag) {//找到了，开始修改
            temp.setName(node.getName());
            temp.setNickName(node.getNickName());
        } else {//没有找到
            System.out.printf("没有找到编号为%d节点，不能修改\n", node.getNo());
        }

    }


    /**
     * 添加时按照排序进行添加
     *
     * @param node
     */
    public void addByOrder(Node node) {
        Node temp = head;
        boolean flag = false;//标示添加的编号是否存在
        while (true) {
            if (temp.getNextNode() == null) {//temp在链表的最后
                break;
            }
            if (temp.getNextNode().getNo() > node.getNo()) {//位置找得到了
                break;
            } else if (temp.getNextNode().getNo() == node.getNo()) {//希望添加的编号已经存在
                flag = true;
                break;
            }
            temp = temp.getNextNode();
        }

        if (flag) {
            System.out.println("准备插入的数据:" + node + "已经存在，不能再次添加");
        } else {
            //插入到链表中
            node.setNextNode(temp.getNextNode());
            temp.setNextNode(node);
        }
    }

    public void delete(int no) {
        Node temp = head;
        boolean flag = false;//标示是否找到
        while (true) {
            if (temp.getNextNode() == null) {//已经到链表的最后
                return;
            }
            if (temp.getNextNode().getNo() == no) {
                flag = true;
                break;
            }
            temp = temp.getNextNode();
        }
        if (flag) {
            temp.setNextNode(temp.getNextNode().getNextNode());
        } else {
            System.out.printf("要删除的节点不存在 节点%d 删除失败", no);
        }


    }

    /**
     * 链表的查询
     *
     * @param no
     * @return
     */
    public Node get(int no) {
        Node temp = head.getNextNode();
        boolean flag = false;
        while (true) {
            if (temp == null) {//链表遍历结束
                break;
            }
            if (temp.getNo() == no) {
                flag = true;
                break;
            }
            temp = temp.getNextNode();
        }
        if (flag) {
            return temp;
        } else {
            return null;
        }
    }



    /**
     * 返回头节点
     *
     * @return
     */
    public Node getHead() {
        return head;
    }

}

//定义一个Node ,没一个Node 就是一个节点
class Node {
    private int no;
    private String name;
    private String nickName;
    private Node nextNode;

    public Node(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }

    public void setNextNode(Node nextNode) {
        this.nextNode = nextNode;
    }

    public Node getNextNode() {
        return nextNode;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getNickName() {
        return nickName;
    }

    public void setNickName(String nickName) {
        this.nickName = nickName;
    }
}
